P4555 [国家集训队]最长双回文串

显然是一道回文自动机板题。

设 $L[i]$ 表示以 $i$ 号点为左端点的最长回文串 ， $R[i]$ 表示以 $i$ 号点为右端点的最长回文串。

$L[i]$ 可以通过将回文串倒过来建自动机求得 ， $R[i]$ 可以直接用原回文串建自动机求得。

最后答案为

$Ans=max(R[i]+L[i+1]) ~~~ (i<n-1)$

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;

const int MAXN = 100000 , MAXK = 26;
struct Palindrome_Automaton {
    int Size , Last , Root0 , Root1 , Trans[ MAXN + 5 ][ MAXK + 5 ] , Link[ MAXN + 5 ];
    int n , Str[ MAXN + 5 ];
    int Len[ MAXN + 5 ] , L[ MAXN + 5 ] , R[ MAXN + 5 ];

    void Init( ) {
        n = 0 , Size = 0;
        memset( Trans , 0 , sizeof( Trans ) );
        memset( Link , 0 , sizeof( Link ) );
        memset( Len , 0 , sizeof( Len ) );

        Root0 = Size ++ , Root1 = Size ++; Last = Root1;
        Len[ Root0 ] = 0  , Link[ Root0 ] = Root1;
        Len[ Root1 ] = -1 , Link[ Root1 ] = Root1;
    }
    
    int Extend( int ch ) {
        int u = Last; Str[ ++ n ] = ch;
        for( ; Str[ n ] != Str[ n - Len[ u ] - 1 ] ; u = Link[ u ] );
        if( !Trans[ u ][ ch ] ) {
            int Newnode = ++ Size , v = Link[ u ];
            Len[ Newnode ] = Len[ u ] + 2;
            for( ; Str[ n ] != Str[ n - Len[ v ] - 1 ] ; v = Link[ v ] );
            Link[ Newnode ] = Trans[ v ][ ch ]; Trans[ u ][ ch ] = Newnode;
        }
        Last = Trans[ u ][ ch ];
        return Len[ Last ];
    }
    void Build1( char *str ) {
        Init( );
        int len = strlen( str );
        for( int i = 0 ; i < len ; i ++ )
            R[ i ] = Extend( str[ i ] - 'a' + 1 );
    }
    void Build2( char *str ) {
        Init( );
        int len = strlen( str );
        for( int i = len - 1 ; i >= 0 ; i -- )
           L[ i ] = Extend( str[ i ] - 'a' + 1 );
    }

    int Calc( char *str ) {
        int Ans = 0 , len = strlen( str );
        for( int i = 0 ; i < len - 1 ; i ++ )
            Ans = max( Ans , R[ i ] + L[ i + 1 ] );
        return Ans;
    }
}PAM;

char str[ MAXN + 5 ];
int main() {
    scanf("%s", str );
    PAM.Build1( str );
    PAM.Build2( str );
    printf("%d", PAM.Calc( str ) );
    return 0;
}